package leecode;

public class LeetCode29 {
    //丑数
    public int nthUglyNumber(int n) {
        int[] arr=new int[n];
        arr[0]=1;
        //任意一个丑数都是由小于它的某一个丑数*2，*3或者*5得到的

        //把a,b,c作为三个指针
        int a=0;
        int b=0;
        int c=0;
        for (int i = 1; i < n; i++) {
            int tmp=Math.min(Math.min(arr[a]*2,arr[b]*3),arr[c]*5);
            if(tmp==arr[a]*2){
                a++;
            }
            if(tmp==arr[b]*3){
                b++;
            }
            if(tmp==arr[c]*5){
                c++;
            }
            arr[i]=tmp;
        }
        return arr[n-1];
    }

    public static void main(String[] args) {
        LeetCode29 leetcode29=new LeetCode29();
        leetcode29.nthUglyNumber(10);
    }
}
